\subsection{Uniform sampling from symmetric difference}
\label{sec:sym_diff_sampling}

We now restate and prove our result on a
communication-efficient protocol to sample from the
symmetric difference of two sets.

\tccSample

We now explain how we obtain a communication-efficient protocol to
sample from the symmetric difference $A \oplus B$ of two sets $A, B
\subseteq [k]$, proving Theorem \ref{thm:sym_diff_sampling}.

Out starting point is Nisan and Safra's protocol \cite{Nisan93} to
determine the least $i$ such that $i \in A \oplus B$. (In
\cite{Nisan93} the protocol is phrased as deciding if $A > B$, when
$A$ and $B$ are viewed as $k$-bit integers. It is easy to switch
between the two.) For uniform sampling from $A \oplus B$, our idea is
to first let the parties permute their sets according to a random
permutation $\sigma$, then run Nisan and Safra's protocol. This
results in an explicit protocol for uniform generation from $A \oplus
B$ with communication $O(\log k/\eps)$ that uses \emph{public
  coins}. A standard transformation to private coins via
\cite{Newman91} results in a protocol that is not explicit.

To obtain an explicit, private-coin protocol we derandomize the space
of random permutations $\sigma$.  The key idea is that it is
sufficient to have a distribution on permutations $\sigma$ such that,
for any set $D = A \oplus B$, any element in $D$ has roughly the same
probability of \emph{being the first element in $D$ to appear in the
  sequence} $\sigma(1), \sigma(2), \sigma(3), \ldots$. We then
construct such a space of permutations with seed length $O(\lg^{3/2}
(k/\eps))$ using Lu's pseudorandom generator for combinatorial
rectangles \cite{Lu02}
(cf.~\cite{Nis92,NiZ96,INW94,EvenGLNV98,ArmoniSWZ96,Lu02,Viola-rbd}).
Plugging a better pseudorandom generator for combinatorial rectangles
in our argument would result in a protocol for uniform sampling from
$A \oplus B$ with communication $\tilde O(\log k/\epsilon)$ and error
$\epsilon$.


As a first step, we have the following simple
derandomization of Nisan and Safra's protocol
\cite{Nisan93}, essentially from \cite{Viola-ccsum}.

\begin{lemma} \label{lemma:NisanSafraViola}
There is an explicit, private-coin protocol to determine
the least $i \in A \oplus B$, where $A, B \subseteq [k]$,
with error $\alpha$ and communication $O(\lg(k/\alpha)
\lg \lg k) = \tilde O(\lg k/\alpha)$.
\end{lemma}
\iflong
\begin{proof}[Proof sketch]
Nisan and Safra's protocol amounts to walking for $O(\lg
k/\alpha)$ on a certain binary tree. At every node, the
two parties just need to determine with error
probability, say, $1/100$ if a portion of their inputs
are different. This latter task can be achieved using
small-bias generators with public randomness $O(\lg k)$
and communication $O(1)$.\cite{NaN93,AGHP92}

The resulting protocol can be seen as a randomized
algorithm needing a one-way stream of $R := O(\lg
k/\alpha) \lg k$ random bits and using space $S := O(\lg
k/\alpha)$ to store the current node.

Nisan's space-bounded generator \cite{Nis92} can reduce
the randomness to $S \lg(R/S) = \lg(k/\alpha) \lg \lg k$
with error loss $2^{-S} = \alpha/k$.

The parties start by exchanging a seed for Nisan's
generator, and then proceed with the previous protocol.
\end{proof}
\fi

\iffalse

Let $\sigma:[n] \rightarrow [n]$ be a permutation of
$[n]$. For a bit string $X \in \{0,1\}^n$, we denote by
$\sigma(X)$ the bit string obtained by permuting $X$ by
$\sigma$, i.e., $\sigma(X)_i = X_{\sigma(i)}$.

Let $A \subseteq [n], B\subseteq [n]$ be represented by
their characteristic vectors of length $n$, and $D = (A
\setminus B) \cup (B \setminus A)$ denote their symmetric
difference. It is immediate that if we choose $\sigma$
uniformly at random from the set of all possible
permutations of $[n]$ and $i$ be the first position where
$\sigma(A)$ and $\sigma(B)$ differ, then $\sigma(i)$ is a
uniform random element of $D$. For $j,k \in [n]$ and $j
\neq k$, we say $j$ {\em precedes} $k$ in $\sigma$ if
$\sigma^{-1}(j) < sigma^{-1}(k)$. It is also not hard to
see that if $\sigma$ be chosen from a distribution over
permutations of $[n]$ such that every element $j \in D$
has probability $\frac{1}{|D|}$ of preceding all other
elements of $D$ in $\sigma$, then $\sigma(i)$ is again a
uniform random element of $D$ where, as before, $i$ is
the first position where $\sigma(A)$ and $\sigma(B)$
differ.

Now we can present the high level description of our
protocol. It has two steps. In the first step, Alice and
Bob generate a permutation $\sigma$ of $[n]$ such that
every element of $D$ has approximately equal probability
of preceding all other elements of $D$ in $\sigma$. In
the second step, they compute the first index $i$ where
$\sigma(A)$ and $\sigma(B)$ differ, if such an index
exists. The output of the protocol is simply $\sigma(i)$,
or $\perp$ if no such index exists.

Using a nice technique of Feige et al.~\cite{FPRU94},
Nissan showed in his beautiful paper~\cite{Nisan93} how
to achieve the second step explicitly using $O(\log n +
\log(\frac{1}{\epsilon}))$ bits communication where the
probability of failure, taken over the random choices of
the protocol, is at most $\epsilon$. Nissan's protocol
works in the public-coin model. Viola~\cite{Viola11}
showed how to make it work in the private-coin model
still keeping it explicit and again using $O(\log n +
\log(\frac{1}{\epsilon}))$ bits communication. The second
step of our protocol will be implemented using Viola's
protocol setting the error parameter to be
$\frac{\epsilon}{3}$.

\fi

Specifically, for given $k$ and $\epsilon$ as in Theorem
\ref{thm:sym_diff_sampling} we set $d = k \log
\left(\frac{3k}{\epsilon}\right)$ and $\alpha :=
\epsilon/3kd$. Alice then picks a random seed of length
$s(k,d,\alpha)$ for a generator that fools every
combinatorial rectangle with universe size $k$ and $d$
dimensions with error $\alpha$. That is, if $X$ is the
output of the generator on a random seed, we have, for
every set $R := R_1 \times R_2 \times \cdots R_d
\subseteq [k]^d$,
$$| \Pr[X \in R] - |R|/k^d| \le \alpha.$$

Alice sends the seed to Bob.

Both Alice and Bob expand the seed into a sample $X$ of
the generator, and use $X$ to generate a permutation
$\sigma$ as follows. Let the number of distinct elements
of $[k]$ that appear in $X$ be $t$. The permutation
$\sigma$ is constructed by defining $\sigma(i)$ to be the
$i$'th distinct element of $[k]$ that appears in $X$ as
we scan it from the beginning, for $i \leq t$. For every
$i
> t$, $\sigma(i)$ is defined to be a distinct element not
appearing in $X$ in an arbitrary but deterministic way
that is fixed before the start of the protocol and both
Alice and Bob are aware of it. (For concreteness, it can
simply be to assign the elements not appearing in $X$ by
order).

\iffalse

The goal is to somehow generate the string $X$ensuring th
at every element of $D$ has approximately equal
probability of preceding all other elements of $D$ in the
permutation $\sigma$ constructed from $X$.

In order to explain how is the string $X$ generated, we
need some machinery from pseudo-random generators. We
start with some definitions which are taken
from~\cite{Lu02}.

\begin{definition}[Volume of a set]
Let $V$ be a finite set. The volume of a set $W \subseteq
V$ is defined as
\[ \vol(W) = \Pr_{x \in V}[x \in W] = \frac{|W|}{|V|}. \]
\end{definition}

Let $\mathcal{W}$ be a family of subsets of $V$. We want
to be able to approximate the volume of any subset $W \in
\mathcal{W}$ by sampling from a much smaller set, instead
of from $V$.

\begin{definition}[$\epsilon$-Generator]
\label{def:generator} We call a deterministic function
$g:\{0,1\}^\ell \rightarrow V$ an $\epsilon$-generator
using $\ell$ bits for $\mathcal{W}$, if for all $W \in
\mathcal{W}$,
\[ |\Pr_{y \in \{0,1\}^\ell}[g(y) \in W] - \vol(W)| \leq \epsilon. \]
\end{definition}

\begin{definition}[Combinatorial rectangle]
\label{def:comb_rect} For positive integers $n$ and $d$,
a combinatorial rectangle of type $(n,d)$ is a subset of
$[n]^d$ of the form $R_1 \times \ldots \times R_d$, where
each $R_i \subseteq [n]$. Let $\mathcal{R}(n,d)$ denote
the family of all such rectangles. The volume of a
rectangle $R \in \mathcal{R}(n,d)$ is $\prod_{i \in d}
\frac{|R_i|}{n}$.
\end{definition}

It is easy to show that a random functon mapping from
$O(\log n + \log d + \log (\frac{1}{\epsilon}))$ to
$[n]^d$ is very likely to be an $\epsilon$-generator for
$\mathcal{R}(n,d)$. Lu~\cite{Lu02} showed an explicit
construction of $\epsilon$-generator for
$\mathcal{R}(n,d)$ using $O(\log n + \log d +
\log^{\frac{3}{2}} (\frac{1}{\epsilon}))$ bits.

Now we are ready to describe how $X$ is generated. First
Alice chooses a uniform random seed in $\{0,1\}^\ell$
where $\ell = O(\log n + \log d + \log^{\frac{3}{2}}
(\frac{3nd}{\epsilon}))$ (recall $d = n \log
\left(\frac{3n}{\epsilon}\right)$), and sends it to Bob.
Both Alice and Bob then runs Lu's
$\frac{\epsilon}{3nd}$-generator for $\mathcal{R}(n,d)$
with this seed and the output of the generator is $X$.

Before proving the correctness of our protocol, let us
compute the number of bits of communication used by it.
The number of bits Alice sends to Bob in the first step
is $O(\log n + \log d + \log^{\frac{3}{2}}
(\frac{3nd}{\epsilon})) = O(\log^{\frac{3}{2}} n +
\log^{\frac{3}{2}} (\frac{1}{\epsilon}))$. The number of
bits that need to be communicated in the second step is
$O(\log n + \log(\frac{3}{\epsilon}))$. Thus the overall
communication for our protocol is $O(\log^{\frac{3}{2}} n
+ \log^{\frac{3}{2}} (\frac{1}{\epsilon}))$ bits, as
claimed in Theorem~\ref{thm:sym_diff_sampling}.

\fi

To show the correctness of our protocol we need the
following lemma.

\begin{lemma}
\label{lem:permutation} Let $X \in [k]^d$ be the output
of a combinatorial rectangle generator with error $\alpha
= \epsilon/3kd$, over a uniform seed. Let $D$ be any set,
and let $j$ be any element in $D$. The probability that
$j$ appears in a coordinate of $X$ before any other
element of $D$ is $\geq \frac{1}{|D|} -
\frac{2\epsilon}{3k}$.
\end{lemma}
\iflong
\begin{proof}
\iffalse
 The probability that $j$ precedes all other
elements of $D$ in $\sigma$ is at least as large as the
probability that $j$ precedes all other elements of $D$
in $\sigma$ and $j$ appears in $X$. The latter
probability is exactly equal to the probability that $j$
is the first among all elements of $D$ to appear in $X$,
which by the property of the
$\frac{\epsilon}{3nd}$-generator for combinatorial
rectangles is at least \fi

We note that the desired probability is the union of
disjoint rectangles, and then apply the property of the
generator:
%\[ \vol(\{j\} \times [k]^{d-1}) \ - \ \frac{\epsilon}{3kd} \ + \ \vol(([k] \setminus D) \times \{j\} \times [k]^{d-2}) \ - \ \frac{\epsilon}{3kd}
%\ + \ldots + \ \vol(([k] \setminus D)^{d-1} \times \{j\}) \ - \ \frac{\epsilon}{3kd} \]
\begin{align*}
%\lefteqn{\Pr\left[X \in \{j\} \times [k]^{d-1} \bigcup ([k] \setminus D) \times \{j\} \times [k]^{d-2} \bigcup \ldots \bigcup ([k] \setminus D)^{d-1} \times \{j\}\right]} && \\
\lefteqn{\Pr\left[X \in \bigcup_{0 \leq t < d} ([k] \setminus D)^t \times \{j\} \times [k]^{d-t-1} \right]} && \\
& = \sum_{0 \leq t < d} \Pr\left[X \in ([k] \setminus D)^t \times \{j\} \times [k]^{d-t-1}\right]\\
& \ge  \sum_{0 \leq t < d} |([k] \setminus D)^t \times \{j\} \times [k]^{d-t-1}|/k^d - \frac{\epsilon}{3k}\\
& =  \frac{1}{k} + \left(\frac{k-|D|}{k}\right) \frac{1}{k} + \ldots + \left(\frac{k-|D|}{k}\right)^{d-1} \frac{1}{k} - \frac{\epsilon}{3k} \\
& =  \frac{1}{k} \left(1 + \left(1-\frac{|D|}{k}\right) + \ldots + \left(1-\frac{|D|}{k}\right)^{d-1} \right) - \frac{\epsilon}{3k} \\
& =  \frac{1}{|D|} \left(1 - \left(1-\frac{|D|}{k}\right)^d \right) - \frac{\epsilon}{3k} \\
& \geq  \frac{1}{|D|} \left(1 - e^{-\frac{|D|}{k} k \log(\frac{3k}{\epsilon})}\right) - \frac{\epsilon}{3k} \\
& =  \frac{1}{|D|} - \frac{1}{|D|} \left(\frac{\epsilon}{3k}\right)^{|D|} - \frac{\epsilon}{3k} \\
& \geq  \frac{1}{|D|} - \frac{2\epsilon}{3k},
\end{align*}
since $|D| \geq 1$.
\end{proof}
\fi
Now we can complete the proof of
Theorem~\ref{thm:sym_diff_sampling}.

\begin{proof}[Proof of
Theorem~\ref{thm:sym_diff_sampling}] For given
$k,\epsilon$, we set $d = k \log
\left(\frac{3k}{\epsilon}\right)$ and $\alpha :=
\epsilon/3kd$. Alice then picks a random seed of length
$s(k,d,\alpha)$.

If $\sigma$ is chosen such that every element $j \in D$
has probability $\frac{1}{|D|}$ of preceding all other
elements of $D$, then $\sigma(i^*)$ is a uniform random
element of $D$, where $i^*$ is the first position where
the permuted $A$ and $B$ differ. Using
Lemma~\ref{lem:permutation}, we immediately see that if
$\sigma$ is chosen as in the first step of the protocol,
then the distribution of $\sigma(i^*)$ is at most
$\left(\frac{2\epsilon}{3k}\right) |D| \leq
\frac{2\epsilon}{3}$-far from the uniform distribution on
$D$.

For the second part of the protocol we use Lemma
\ref{lemma:NisanSafraViola} with $\alpha := \epsilon/3$.

Overall, the sampled distribution has distance $\le 2\epsilon/3
+ \epsilon/3 = \epsilon$ from the uniform distribution on $D$.

Using the generator in \cite{Lu02} we have $s(k,d,\alpha)
= O(\lg n + \lg d + \lg^{32} 1/\alpha) = O (\lg^{3/2}
n/\epsilon)$. So overall the communication is
$O(\lg^{3/2} n/\epsilon)$.
\end{proof}
